/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
/* 
方法思路
定义 DP 数组：创建一个二维数组dp，其中dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最少操作次数。
初始化边界条件：
dp[0][0] = 0：两个空字符串之间的编辑距离为 0。
dp[i][0] = i：将word1的前i个字符转换为空字符串需要i次删除操作。
dp[0][j] = j：将空字符串转换为word2的前j个字符需要j次插入操作。
状态转移方程：
当word1[i-1] === word2[j-1]时，dp[i][j] = dp[i-1][j-1]，即不需要额外操作。
当word1[i-1] !== word2[j-1]时，dp[i][j]取以下三种操作的最小值加 1：
插入：dp[i][j-1] + 1
删除：dp[i-1][j] + 1
替换：dp[i-1][j-1] + 1
返回结果：dp[m][n]即为将word1转换为word2所需的最少操作次数，其中m和n分别是word1和word2的长度。

代码解释
初始化 DP 数组：创建一个(m+1) x (n+1)的二维数组dp，其中dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最少操作次数。
处理边界条件：初始化第一行和第一列，表示将空字符串转换为另一个字符串所需的操作次数。
填充 DP 数组：遍历每个字符，根据当前字符是否相等更新dp数组的值。如果相等，则不需要额外操作；否则，选择插入、删除或替换操作中的最小次数加 1。
返回结果：返回dp[m][n]，即整个字符串的编辑距离。
*/
var minDistance = function (word1, word2) {
  const m = word1.length;
  const n = word2.length;

  // 创建DP数组并初始化
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  // 初始化边界条件
  for (let i = 0; i <= m; i++) {
    dp[i][0] = i;
  }
  for (let j = 0; j <= n; j++) {
    dp[0][j] = j;
  }

  // 填充DP数组
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1,    // 删除操作
          dp[i][j - 1] + 1,    // 插入操作
          dp[i - 1][j - 1] + 1 // 替换操作
        );
      }
    }
  }

  return dp[m][n];
};